package cn.genmer.test.security.leetcode.easy;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @program: Algorithm_to_practice
 * @description: 217. 存在重复元素
 * 给定一个整数数组，判断是否存在重复元素。
 *
 * 如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
 * @author: Genmer
 * @create: 2020-10-16 23:59
 **/
public class DuplicateArray {
    public static void main(String[] args) {
        int[] nums = {0,2,1,5,4,7};
        System.out.println(containsDuplicate(nums));
    }

    /**
     * 朴素线性查找
     * leetcode会超时 - 一般而言，如果一个算法的时间复杂度为 O(n^2)O(n2)，它最多能处理 nn 大约为 10^4的数据。当 nn 接近 10^5时就会超时。
     * @param nums
     * @return
     */
    public static boolean containsDuplicate(int[] nums) {
        int roundCount=0;
     while (roundCount <nums.length){
         for (int i=0;i<nums.length;i++){
            if (roundCount== i) {
                continue;
            }
            else {
                if (nums[roundCount] == nums[i]) return true;
            }
         }
         roundCount++;
     }
        return false;
    }

    /**
     * 排序查找
     * 本方法使用排序算法。由于比较排序算法，如堆排序，可以在最坏情况下具有 O(n \log n)O(nlogn) 的时间复杂度。
     * 因此，排序经常是很好的预处理方法。排序之后，我们可以扫描已排序的数组,以查找是否有任何连续的重复元素。
     * @param nums
     * @return
     */
    public static boolean containsDuplicate2(int[] nums) {
        Arrays.sort(nums);
        for (int i=0;i<nums.length-1;i++){
            if (nums[i] == nums[i+1]) return true;
        }
        return false;
    }

    public static boolean containsDuplicate3(int[] nums) {
        HashSet<Integer> set = new HashSet<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            if (!set.add(nums[i])) {
                return true;
            }
        }
        return false;
    }
}
